/**
 * @file 46.Permutations.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-14
 * 
 * @copyright Copyright (c) 2021
 * 
 * 排列问题
 * 46.全排列
 * 47.全排列II
 */

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

template <typename T>
void print(const T &Containers)
{
    typename T::const_iterator it = Containers.begin();
    while (it != Containers.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

class Solution
{
private:
    vector<vector<int>> res;
    vector<int> path;

public:
    // 46. nums无重复，求所有全排列
    vector<vector<int>> permute(vector<int> &nums)
    {
        // 不在需要start idx,因为每次都要从头开始取数
        vector<bool> used(nums.size(), false);
        backtracking46(nums, used);
        return res;
    }

private:
    void backtracking46(vector<int> &nums, vector<bool> &used)
    {
        if (path.size() == nums.size()) {
            res.emplace_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            path.push_back(nums[i]);
            backtracking46(nums, used);
            used[i] = false;
            path.pop_back();
        }
    }

public:
    // 47. nums有重复，求不重复的全排列
    vector<vector<int>> permuteUnique(vector<int> &nums)
    {
        vector<bool> used(nums.size(), false);
        std::sort(nums.begin(), nums.end());
        backtracking47(nums, used);
        return res;
    }

private:
    void backtracking47(vector<int> &nums, vector<bool> &used)
    {
        if (path.size() == nums.size()) {
            res.emplace_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (used[i]) {
                continue;
            }
            // used[i-1]=False 同一层上    过滤掉相同元素 
            // used[i-1]=True  同一树枝上  不过滤相同元素
            // 其实加上used[i-1]==false是为了让同一树枝上相同元素，不被continue掉
            // 而同一层的相同元素是==true的，会被continue掉
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            used[i] = true;
            path.push_back(nums[i]);
            backtracking47(nums, used);
            used[i] = false;
            path.pop_back();
        }
    }
};

Solution solve = Solution();
void test46()
{
    vector<int> nums = {1, 2, 3}; // 无重复
    auto res = solve.permute(nums);
    for (auto &r : res) {
        print(r);
    }
}
void test47()
{
    vector<int> nums = {1, 1, 2}; // 有重复
    auto res = solve.permuteUnique(nums);
    for (auto &r : res) {
        print(r);
    }
}
int main()
{
    // test46();
    test47();
    return 0;
}